/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 *https://leetcode.cn/problems/merge-k-sorted-lists/
 * 思路：这个方法和前两种方法的思路有所不同，我们需要维护当前每个链表没有被合并的元素的最前面一个，k个链表就最多有 k 个满足这样条件的元素，
 * 每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，我们可以用优先队列来优化这个过程。
 *

 */
class MergeKLists {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap=new PriorityQueue<>(new Listcmp());//成员是链表，需要自定义比较器
        ListNode newHead=new ListNode();//头结点
        ListNode cur=newHead;
        for(ListNode node:lists){//构造小跟堆
            if(node!=null)
            minHeap.offer(node);
        }
        while(!minHeap.isEmpty()){
            ListNode tmp=minHeap.poll();
            cur.next=tmp;
            tmp=tmp.next;
            cur=cur.next;
            if(tmp!=null){//如果后面还有，入堆
                minHeap.offer(tmp);
            }
        }
        return newHead.next;
    }
}
class Listcmp implements Comparator<ListNode>{

    @Override
    public int compare(ListNode o1, ListNode o2) {
        return o1.val-o2.val;
    }
}